package com.owulia.leetcode.num;

public class BinarySearch {
    public static int search(int[] nums, int target) {

        int length = nums.length;

        int middle = length / 2;
        int start = 0;
        int end = length;
        while (end - start > 0) {
            if (nums[middle] == target) {
                return middle;
            } else if (nums[middle] > target) {
                end = middle - 1;
            } else {
                start = middle + 1;
            }
            middle = (start + end) / 2;
        }
        if (start < length && start == end && nums[start] == target) {
            return end;
        }
        return -1;
    }


    public static void main(String[] args) {

        /*int[] nums = {2, 5};
        int target = 5;
        System.out.println(search(nums, target));*/


        System.out.println(firstBadVersion(2126753390));
    }


    public static int firstBadVersion(int n) {
        int length = n;
        int middle = length / 2;
        int start = 0;
        int end = length;
        while (end - start > 0) {
            if (isBadVersion(middle)) {
                if (middle == 0 || !isBadVersion(middle - 1)) {
                    return middle;
                }
                end = middle - 1;
            } else {
                start = middle + 1;
            }
            middle = (start / 2 + end / 2) + (start % 2 + end % 2) / 2;
        }
        return middle;
    }

    public static boolean isBadVersion(int middle) {
        if (middle >= 1702766719) {
            return true;
        }
        return false;
    }


    public int searchInsert(int[] nums, int target) {
        int n = nums.length;
        int left = 0, right = n - 1, ans = n;
        while (left <= right) {
            int mid = ((right - left) >> 1) + left;
            if (target <= nums[mid]) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }


    public int search1(int[] nums, int target) {
        int mid = nums.length / 2;
        int start = 0;
        int end = nums.length;

        while (end - start > 0) {
            if (target == nums[mid]) {
                return mid;
            } else if (target > nums[mid]) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
            mid = (start + end) / 2;
        }
        if (nums[start] == target) {
            return start;
        }
        return -1;
    }

}
